교착 상태에 대해서 설명해주세요.

DeadLock

멀티 프로그래밍 환경 또는 멀티 스레드 환경에서는 여러 프로세스 또는 스레드가 한정된 자원을 동시에 사용하기위해 항상 경쟁 상태에 놓여 있다. 어떤 이유로든 프로세스가 필요한 자원을 획득하지 못하고 영원히 자원을 기다리는 상태로 남아있는 것을 데드락이라고 한다.

운영체제에서 데드락(교착상태)이란, 두개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해서 다음 처리를 하지 못하는 상태이다.

마치, 외나무 다리의 양 끝에서 서로가 비켜주기를 기다리고 있는 것과 같다.

즉 둘이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황을 말한다. 자원을 획득하지 못하고 있다는 점에서 기아 상태(starvation state)와 비슷하지만 이것은 영원히 헤어나올 수 없는 상태라는 점에서 차이가 있다.

두 프로세스가 서로 종료될 때까지 대기하는 프로그램을 실행한다고 생각해보자. 프로세스 A는 B가 종료될 떄까지, 프로세스 B는 A가 종료될 때까지 작업을 하지 않기 때문에 프로그램은 어떤 동작도 하지 못한다. 이처럼 두 프로세스가 리소스를 점유하고 놓아주지 않거나, 어떠한 프로세스도 리소스를 점유하지 못하는 상태가 되어 프로그램이 멈추는 현상을 데드락(Deadlock)이라고 한다. 운영체제도 결국 소프트웨어이기 때문에 데드락에 빠질 수 있다.

발생 조건

상호 배제(Mutual Exclusion): 한번에 프로세스 하나만 자원을 사용할 수 있다. 공유되지 않는 자원이란 한번에 딱 하나의 프로세스만이 소유할 수 있는 자원이다. 만일 이 자원이 어떤 프로세스에게 할당되어 있는 중 다른 프로세스가 이 자원에 할당을 요청(Request)하면 그 다른 프로세스는 현재 프로세스가 자원을 반환할 때까지 대기 상태에 있게된다.
점유와 대기(Hold and Wait): 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야한다.
비선점(Non Preemption): 이미 할당된 자원을 강제로 빼앗을 수 없다. 자원을 획득함에 있어서 우선권이 없다. 그 어떤 프로세스도 다른 프로세스가 소유하고 있는 자원을 강제로 빼앗아 올 수 없다. 자원을 획득할 수 있는 유일한 방법은 다른 어떤 프로세스도 해당 자원을 점유하고 있지 않을 때 뿐이다.
순환 대기(Circular Wait): 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다. 프로세스들이 상대방이 필요한 자원을 점유한 상태로 상대방이 가지고 있는 자원을 요청하고 있는 상태이다. 예를 들어 프로세스 P1, P2, P3이 있다면 P1은 P2가 가지고 있는 자원이 해제 되길 기다리고, P2는 P3이 가진 자원, P3는 그다음..과 같은 형식으로 가장 마지막 프로세스의 Pn가 다시 P1이 가진 자원을 요청하고 해제 되길 기다리는 형태가 아래 그림처럼 하나의 순환 구조를 이룬다.

데드락이 발생하기 위해서는 위의 네가지 조건이 모두 만족되어야 한다. 데드락에 빠지는 필요 조건이 네가지나된다고 하니 데드락 상태에 빠지기 쉽지 않다고 생각할 수 있다. 하지만 의외로 쉽게 모든 데드락 조건이 만족된다.

데드락 방지(Deadlock Prevention)

데드락 방지 기본 개념의 출발은 간단한다. 위에서 네가지 조건이 모두 만족되어야 한다고 했다. 그러면 그 중 한가지만 발생하지 못하도록 막으면 된다.

상호 배제 방지(Mutual Exclusion Prevention)

상호배제라는 것은 공유가 불가능한 자원을 소유하고 있는 것을 말한다. 그렇다면 자원을 공유 가능하도록 만들면 데드락은 발생하지 않는다. Read-only 파일이 좋은 예이다. 만일 업데이트가 필요 없는 파일이면 Read-only 권한으로 자원을 점유할 수 있다. 파일에 변경이 없으니 여러 프로세스가 동시에 이 파일에 접근이 가능하고, 이는 자원을 점유하기 위해 대기하는 프로세스가 없다는 뜻이다. 이로써 상호배제 조건이 만족하지 않으므로 데드락은 발생할 수 없다.

점유와 대기 방지(Hold and Wait Prevention)

점유 대기란 프로세스가 자원을 소유한 상태에서 다른 자원을 추가 요청하기 때문에 발생한다. 만일 한 프로세스가 동시에 점유할 수 있는 자원이 하나로 제한된다면 다른 자원을 획득하기 위해서는 가지고 있는 자원을 해제해야 하기 때문에 점유와 대기 상태는 발생하지 않는다. 하지만 여러 자원에 대한 일관성을 보장해야하는 작업의 경우에는 여러 자원을 동시에 접근하여 업데이트 해야만 하므로 이 방법을 적용할 수 없다. 일관성을 보장하기 위한 방법으로는 마치 여러 자원들을 하나의 묶음처럼 필요한 자원을 모두 한번에 할당할 수도 있다. 하지만 이 방법 역시 당장 사용하지 않는 자원을 작업이 끝날 때 까지 불필요하게 점유하고 있을 수 있는 성능상 단점이 있다.

순환 대기 방지(Circular Wait Prevention)

순환 대기 상태는 내가 필요한 자원을 다른 프로세스에서 선점하고 있고, 그 다른 프로세스가 필요한 자원을 내가 선점하고 있을 때 발생한다. 이를 방지하는 첫번째 방법은, 모든 프로세스가 획득하는 자원의 순서를 동일하게 맞추는 것이다. 모든 자원마다 고유의 번호를 부여하고 필요한 자원을 번호가 작은 것부터 큰 순서대로 획득하도록 한다면 추가로 필요한 자원들이 어떠한 프로세스에게도 점유되어 있지 않음을 보장한다.